package java_core.day;

public class Day5_23 {

    //===============================================================================================

    /**
     * 53.最大子序和 https://leetcode-cn.com/problems/maximum-subarray/
     * 找出一个数组中最大和的连续子数组，返回其最大和
     */
    private static int getNumsMaxSum1_53(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int max = nums[0];
        for (int i = 0; i < nums.length; i++) {
            int preSum = nums[i];
            int nowSum = 0;
            for (int j = i + 1; j < nums.length; j++) {
                nowSum = preSum * nums[j];
                max = Math.max(max, nowSum);
                preSum = nowSum;
            }
            max = Math.max(max, nums[i]);
        }

        return max;
    }

    //===============================================================================================

    /**
     * 35 搜索插入位置 https://leetcode-cn.com/problems/search-insert-position/
     * 给定一个无重复数的排序数组和目标值，返回目标值索引，如果不存在，则返回其插入的位置
     */
    private static int getIndex_35(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0] >= target ? 0 : 1;
        }
        if (nums[0] < nums[1]) {
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] >= target) {
                    return i;
                }
            }
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (target >= nums[i]) {
                    return i;
                }
            }
        }
        return nums.length;

    }


    //===============================================================================================
    //509.斐波那契数 https://leetcode-cn.com/problems/fibonacci-number/
    // F(N)=F(N-1)+F(N-2),F(0)=0,F(1)=1
    private static int fib_509(int N) {
        if (N == 0) {
            return 0;
        }
        if (N == 1) {
            return 1;
        }
        return fib_509(N - 1) + fib_509(N - 2);
    }

    //===============================================================================================
    //387 字符串中的第一个唯一字符 https://leetcode-cn.com/problems/first-unique-character-in-a-string/
    private static int getFirstChar_387(String s) {
        if (s == null || s.equals("")) {
            return -1;
        }
        int[] arr = new int[128];
        for (int i = 0; i < s.length(); i++) {
            arr[s.charAt(i)]++;
        }
        for (int i = 0; i < s.length(); i++) {
            if (arr[s.charAt(i)] == 1) {
                return i;
            }
        }

        return -1;

    }

    //===============================================================================================
    //520 检测大写字母 https://leetcode-cn.com/problems/detect-capital/
    // 判断字符串的大写字母使用是否正确
    private static boolean detectCapitalUse_520(String word) {
        if (word == null || word.length() <= 1) {
            return true;
        }
        int count = 0;
        for (int i = 1; i < word.length(); i++) {
            if (isBigLetter(word.charAt(i))) {
                count++;
            }
        }
        if (count == 0) {
            return true;
        }
        //首字母大写且后面字符全是大写
        if (isBigLetter(word.charAt(0)) && count == word.length() - 1) {
            return true;
        }
        return false;
    }

    private static boolean isBigLetter(char c) {
        if (c >= 'A' && c <= 'Z') {
            return true;
        }
        return false;
    }


    //===============================================================================================
    //1013 判断能否将数组分成相等的三个部分（和相等）
    //  https://leetcode-cn.com/problems/partition-array-into-three-parts-with-equal-sum/
    //计算出每个部分需要的和,判断能不能将数组分成三个子数组以上
    private static boolean spliteThree_1013(int[] A) {
        if (A == null || A.length < 3) {
            return false;
        }
        int sum = 0;
        for (int i = 0; i < A.length; i++) {
            sum += A[i];
        }
        if (sum % 3 != 0) {
            return false;
        }
        int count = 0;
        int childSum = 0;
        for (int i = 0; i < A.length; i++) {
            count += A[i];
            if (count == sum / 3) {
                count = 0;
                childSum++;
            }
        }
        // 存在这种情况:[10,-10,10,-10,10,-10,10,-10,10,-10,10,-10], 所以childSum要大于等于3
        if (childSum >= 3) {
            return true;
        } else {
            return false;
        }

    }


    //===============================================================================================
    //1071 字符串的最大公因子 https://leetcode-cn.com/problems/greatest-common-divisor-of-strings/
    /*对于字符串 S 和 T，只有在 S = T + ... + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。
    返回最长字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。
    示例 1：
    输入：str1 = "ABCABC", str2 = "ABC"
    输出："ABC"
    示例 2：
    输入：str1 = "ABABAB", str2 = "ABAB"
    输出："AB"*/

    //即:str1和str2都能由X组成,输出这个X
    public static String getMaxChildString(String str1, String str2) {
        if (str1 == null || str2 == null || str1.equals("") || str2.equals("")) {
            return "";
        }
        //存在最大公因子的时候,str1+str2和str2+str1一定是相等的
        if (!(str1 + str2).equals(str2 + str1)) {
            return "";
        }

        // 辗转相除法求gcd。
        return str1.substring(0, gcd(str1.length(), str2.length()));
    }

    /**
     * gcd算法,求出a和b的最大公因子
     */
    private static int gcd(int a, int b) {
        return b == 0? a: gcd(b, a % b);
    }



    //===============================================================================================
    //1365 有多少小于当前数字的数字 https://leetcode-cn.com/problems/how-many-numbers-are-smaller-than-the-current-number/
    /*输入：[8,1,2,2,3]
    输出：[4,0,1,1,3]*/
    private static int[] getArray_1365(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        int[] arr = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            int count = 0;
            for (int j = 0; j < nums.length; j++) {
                if (j != i && nums[j] < nums[i]) {
                    count++;
                }
            }
            arr[i] = count;
        }

        return arr;
    }


    //===============================================================================================



}
